import java.sql.SQLOutput;
import java.util.HashSet;

/*
题目描述：判断一棵树是否为另一棵树的子结构
 */
public class E26 {
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode('a');
        root1.left = new TreeNode('a');
        root1.right = new TreeNode('b');
        root1.left.left = new TreeNode('b');
        root1.left.right = new TreeNode('c');
        root1.left.right.left = new TreeNode('d');
        root1.left.right.right = new TreeNode('e');

        TreeNode root2 = new TreeNode('a');
        root2.left = new TreeNode('b');
        root2.right = new TreeNode('c');

        boolean res = HasSubtree(root1, root2);


        System.out.println(res);

    }

    public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean res = false;
        if(root1 != null && root2 != null){
            if(root1.value == root2.value){
                res =  DoesTree1HaveTree2(root1, root2);
            }
            if(!res){
                res = HasSubtree(root1.left, root2);
            }
            if(!res){
                res = HasSubtree(root1.right, root2);
            }
        }
        return res;
    }

    public static boolean DoesTree1HaveTree2(TreeNode root1, TreeNode root2){
        if(root2 == null){
            return true;
        }
        if(root1 == null){
            return false;
        }
        if(root1.value != root2.value){
            return false;
        }

        return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
    }
}
